/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.fa;

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

/** Represents an inverse transition function that can be constructed from the
 *  transition function. Thus, this class is helpful for the inversion of 
 *  a transition function. */
public class InverseTransitionFunction {
	// A=table[state][char] is an array of states admitting a transition to "state"
	// an character "char"
	// A[0] specifies the number of array entries actually used.
	private int[][][] table;
	
	/** Constructs the inverse function from the transition function (where
	 *  transitionTable.get(state)[character] is the target state when being in "state"
	 *  and reading a "character").*/
	public InverseTransitionFunction(List<int[]> transitionTable, int alphabetSize) {
		table = new int[transitionTable.size()][alphabetSize][];
		int state = 0;
		for (int[] transitions : transitionTable) {
			for (int c=0; c<alphabetSize; ++c) {
				int[] t = table[transitions[c]][c];
				if (t==null) {
					t = new int[4];
					table[transitions[c]][c]=t;
				} else {
					// array full? --> then double its length
					if (t[0]==t.length-1) {
						int [] tNew = new int[2*t.length];
						System.arraycopy(t, 0, tNew, 0, t.length);
						t=tNew;
						table[transitions[c]][c]=t;
					}
				}
				t[0]+=1;
				t[t[0]]=state;
			}
			++state;
		}
	}
	
	public InverseTransitionFunction(CharacterAutomaton automaton) {
		table = new int[automaton.getStateCount()][automaton.getAlphabetSize()][];
		for (int state=0; state<automaton.getStateCount(); ++state) {
			for (int c=0; c<automaton.getAlphabetSize(); ++c) {
				int targetState = automaton.getTransitionTarget(state, c);
				int[] t = table[targetState][c];
				if (t==null) {
					t = new int[4];
					table[targetState][c]=t;
				} else {
					// array full? --> then double its length
					if (t[0]==t.length-1) {
						int [] tNew = new int[2*t.length];
						System.arraycopy(t, 0, tNew, 0, t.length);
						t=tNew;
						table[targetState][c]=t;
					}
				}
				t[0]+=1;
				t[t[0]]=state;
			}
		}
	}

	private static class InverseImageIterator implements Iterator<Integer> {
		private int[] table;
		private int nextElement;
		InverseImageIterator(int[] table) {
			if (table==null) this.nextElement=-1;
			this.table=table;
			this.nextElement=1;
		}
		public boolean hasNext() { return nextElement>=0; }
		public Integer next() {
			if (nextElement<0) throw new NoSuchElementException();
			int result = table[nextElement];
			if (table[0]>nextElement) ++nextElement; else nextElement=-1;
			return result;
		}
		public void remove() { throw new UnsupportedOperationException(); }
	}
	
	private static class IterableInverseImage implements Iterable<Integer> {
		private int[] table;
		IterableInverseImage(int[] table) {
			this.table=table;
		}
		public Iterator<Integer> iterator() { return new InverseImageIterator(table); } 
	}
	
	/** Returns an Iterable object that allow iteration over elements of a block. */
	public Iterable<Integer> get(int state, int character) {
		return new IterableInverseImage(table[state][character]);
	}
	
	/** Returns true, if the inverse image of the state (w.r.t. the given character)
	 *  is not empty. */
	public boolean hasInverse(int state, int character) {
		return table[state][character]!=null;
	}
}
